package com.rising.face.ali.bishi.findStr;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: rising
 * @Description:
 * @Date: create in 2021/2/28 20:23
 */
public class FindSubStr {
    private static List<String> minSubStrList = new ArrayList<>();

    public static String findMinSubStr(String sourceStr, String targetStr) {
        for (int i = 0; i < sourceStr.length(); i++) {
            findSubStr(sourceStr, targetStr, i);
        }
        if (minSubStrList.isEmpty()) {
            return "";
        }
        String rtnStr = minSubStrList.get(0);
        for (int i = 0; i < minSubStrList.size(); i++) {
            rtnStr = rtnStr.length() > minSubStrList.get(i).length() ?  minSubStrList.get(i) : rtnStr;
        }
        return rtnStr;
    }

    public static void findSubStr(String sourceStr, String targetStr, int index) {
        char[] sourceChars = sourceStr.toCharArray();
        char[] targetChars = targetStr.toCharArray();
        int firstIndex = 0,finalIndex = 0;
        int targetIndex = 0;
        for (int i = index; i < sourceChars.length; i++) {
            if (sourceChars[i] == targetChars[targetIndex] && targetIndex == 0) {
                firstIndex = i;
                targetIndex++;
                continue;
            }
            if (sourceChars[i] == targetChars[targetIndex]) {
                targetIndex++;

                if (targetIndex == targetChars.length) {
                    finalIndex = i;
                    break;
                }
                continue;
            }
        }

        StringBuilder stringBuilder = new StringBuilder("");
        if (finalIndex - firstIndex >= targetChars.length) {

            for (int i = firstIndex; i <= finalIndex; i++) {
                stringBuilder.append(sourceChars[i]);
            }
            minSubStrList.add(stringBuilder.toString());
        }


    }

    public static void main(String[] args) {
        String sourceStr = "BPDAUNZHGAHSIWBADNC";
        String targetStr = "ZAW";
        String minSubStr = findMinSubStr(sourceStr, targetStr);
        System.out.println(minSubStr);
    }

}
